package com.itheima.leetcode.od.c.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * <h3>猜密码</h3>
 */
public class GuessPassword {
    static int[] nums;
    static int level;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        nums = Arrays.stream(sc.nextLine().split(","))
                .mapToInt(Integer::parseInt)
                .toArray();
        level = Integer.parseInt(sc.nextLine());

        System.out.println(getResult());
    }

    public static String getResult() {
        // 按照数值大小升序，这样后续形成的组合的内部就是按照数值大小升序的
        Arrays.sort(nums);

        // 求不重复组合
        ArrayList<String> res = new ArrayList<>();
        backTracking(0, new LinkedList<>(), res);

        if (res.size() > 0) {
            // 组合间按照字典序排序
            return res.stream()
                    .sorted((a, b) -> a.compareTo(b))
                    .collect(Collectors.joining("\n"));
        } else {
            return "None";
        }
    }

    public static void backTracking(int index, LinkedList<String> path, ArrayList<String> res) {
        if (path.size() >= level) {
            // 如果path层数到达level层，则记录该组合
            res.add(path.stream()
                    .collect(Collectors.joining(",")));
        }

        for (int i = index; i < nums.length; i++) {
            // 树层去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            path.push(nums[i] + "");
            backTracking(i + 1, path, res);
            path.pop();
        }
    }
}